
In perioada 4-16 august a fost la Constanta perioada de pregatire si
selectie a lotului de informatica. Au fost 2 baraje (pe 9 si 16 august) in
urma carora au fost selectati elevii care formeaza echipa pentru Balcaniada.
Acestia sunt:

1. Valentin Gheorghita (Ploiesti)
2. Ovidiu Ghiorghioiu  (Alba Iulia)
3. Alin Simpalean      (Medias)
4. Mihai Scortaru      (Cluj)

Problemele date la baraje:


Problema 1 (Agricultura - Petru Pau)

In satul Valea lui Liman a ajuns legea reformei agrare. Fiecare satean s-a
repezit sa caute in sertare sau poduri documente vechi, ramase de la
batrani, pentru a cere cat mai mult pamant. Comisia de stribuire a pamntului
este formata din primar si .. atat. Caci sunt putini oameni ramasi in sat,
si de unde sa aleaga alti membri ?.. Primarul a cerut satenilor sa-si
prezinte in scris pretentiile. Dupa doua zile, cererile taranilor erau
asezate vraf pe biroul primarului. Fiecare familie a cerut un singur lot,
dreptunghiular. Toate loturile au laturile paralele intre ele. Primarul a
primit de la fiecare satean coordonatele colturilor opuse ale lotului cerut.
Oameni intelepti, satenii au evitat sa includa in loturi zonele
mlastinoase, acestea fiind portiuni de teren inconjurate complet de loturi,
nesolicitate de nimeni. Fapt interesant, desi pot exista zone revendicate de
mai multi sateni (si care apartin deci de mai multe loturi), singurele zone
agricole ale satului nerevendicate sunt cele mlastinoase.

Problema:
    Scrieti un program care determina cate astfel de portiuni mlastinoase
se afla in zona satului Valea lui Liman.
Intrare:
    Datele de intrare se gasesc intr-un fisier al carui nume se citeste de
la tastatura. Structura unui fisier de date este:
n       - numarul de loturi solicitate de sateni (1<=n<=200);
a1 b1 c1 d1 - (a1,b1) si (c1,d1) sunt coordonatele colutrilor opuse ale
        lotului din prima cerere
.....
an bn cn dn - (an,bn) si (cn,dn) sunt coordonatele colturilor opuse ale
        lotului din a n-a cerere.
Toate coordonatele sunt numere reale pozitive, iar laturile loturilor sunt
paralele cu axele de coordonate.
    In plus, daca (x1,y1) si (z1,u1) sunt doua varfuri oarecare din doua
loturi diferite, atunci x1<>z1 si y1<>u1.
Iesire:
    Se scrie pe ecran un singur numar intreg k, reprezentand numarul
zonelor mlastinoase din zona satului.
Exemplu:
Pentru intrarea:
5
0.0 0.0 10.1 1.1
0.2 2.0 10.0 3.2
10.4 5.3 0.1 4.3
0.3 0.1 1.0 5.0
10.2 5.1 9.6 0.3
programul va afisa
2

Timp de executie: 1 secunda per test.
-------------------------------

Ziua 1 Problema 2 (Circuite - Iuliu Vasilescu)

Pentru realizarea unui circuit logic se folosesc trei tipuri de conectori
(porti). Anume: OR: Este o poarta logica cu doua intrari si o iesire,
reprezentata grafic prin: |\ -------->\______\ -------->/      / |/ AND: Este de
asemenea o poarta cu doua intrari si o iesire, reprezentata prin |\ ------>|
\______\ ------>| /      / |/ NOT: Aceasta poarta are o singura intrare si o
iesire, fiind notata cu |--| ---->|  |-----> |--| Tabelele de operatii ale
celor trei porti logice sunt:

    OR | 0  1   AND | 0  1  NOT | 0  1
    ---|-------    -----|------    -----|------
     0 | 0  1    0  | 0  0      | 1  0
     1 | 1  1    1  | 0  1

Cu cele trei tipuri de porti se pot face diverse conexiuni, obtinand o
varietate larga de circuite logice. De exemplu:

                |\  c1                      |\
        i1 ---->| \_____+-------------------->\____+----------> o1
        i2 -+-->| /                  +------->/ c4
            |   |/          |--|     |      |/
            |           +---|  |-----+
            |   |\      |   |--| c3
            +---->\_____+________________+--------------------> o2
        i3 ------>/ c2
                |/

                Figura 2

va avea pentru intrarea (i1,i2,i3)=(0,1,0) iesirea (o1,o2)=(0,1).

Problema: Fiind dat un circuit logic construit cu p porti (c1,..,cp) de
tipurile definite mai sus, si cu iesirea (o1,...,om), se cere sa se
construiasca o intrare (i1,..,in) in circuit care sa conduca la iesirea
respectiva. Se considera doar circuite cu porti AND,OR si NOT, fara cicluri
(prin fiecare poarta se trece cel mult odata). Intrare: Fisierul de intrare -
al carui nume este RETEA.IN - contine un singur set de date de test. Forma
specificata a unui set este: Pe prima linie sunt scrise trei numere intregi
pozitive n m p n reprezinta numarul de intrari din circuit notate i1,..,in
1<=n<=250; m reprezinta numarul de iesiri din circuit, notate o1,..,om
1<=m<=250; p reprezinta numarul de porti din circuit, notate c1,..,cp
1<=p<=250. Urmeaza p linii, cate una pentru fiecare poarta logica. Forma
liniei i (care defineste poarta logica ci) este: X a b  unde X este tipul
portii (A pt. AND, O pt. OR, N pt. NOT); a si b formeaza intrarea in poarta
ci; daca X este NOT, atunci intrarea b lipseste; aceste intrari sunt de
forma is sau cs dupa cum ele vin de la intrarea is in circuit sau de la
iesirea portii cs. Urmatoarele doua linii contin cate m elemente fiecare.
Prima este de forma a1 a2 .. am unde fiecare ai reprezinta iesirea oi si
este de forma ck sau ik (dupa cum oi provine direct din poarta ck sau din
intrarea ik); A doua linie este de forma: x1 x2 .. xm    unde fiecare xi este
0 sau 1 si reprezinta valoarea iesirii oi. De exemplu, pentru circuitul
logic din Figura 2, fisierul de intrare este: 3 2 4 A i1 i2 O i2 i3 N c2 O c1 c3
c4 c2 0 1 Iesire: Iesirea este realizata in fisierul RETEA.OUT si consta
dintr-o linie cu n caractere binare 0 sau 1, separate prin cate un spatiu.
Ea reprezinta o intrare in retea, corespunzatoare vectorului (i1,..,in),
care a condus la rezultanta data in fisierul de intrare.

Pentru exemplul de sus, o iesire posibila este:

0 1 0

Timp de lucru: 10 sec/test.
--------------------------------------

Problema 3 (Reprezentarea arborilor - Rodica Pintea)

    Se considera un arbore binar strict (orice nod are exact 0 sau 2
descendenti). Fiecare nod se eticheteaza cu un numar intreg reprezentand
ponderea subarborelui a carui radacina este nodul respectiv (prin pondere
se intelege numarul de frunze ale subarborelui in discutie).
De exemplu, un arbore binar astfel etichetat este:

                                  6
                                /   \
                               4      2
                             /   \   / \
                            2     2  1  1
                           / \   / \
                          1   1 1   1

                Figura 3

Pentru fiecare frunza a arborelui se alege subarborele de pondere maxima a
carui parcurgere in preordine contine pe ultima pozitie frunza respectiva.
Secventa ordonata a acestor ponderi asociate tuturor frunzelor arborelui
vor caracteriza complet arvorele respectiv. Problema: Fiind data secventa
ponderilor subarborilor asociati frunzelor unui arbore, sa se construiasca
arborele respectiv. Intrare: Fisierul de intrare arbore.in va contine maxim 3
seturi de date de test. Fiecare set de date de test este format din doua
linii de forma n p1 p2 .. pn unde n este numarul de frunze ale arborelui
(2<=n<=10000) iar a doua linie reprezinta secventa ordonata de ponderi.
Sfarsitul fisierului de intrare este dat de o linie care contine doar
numarul 0. Iesire: Fisierul arbore.out va contine solutiile testelor din
fisierul arbore.in. Ele vor fi date sub forma reprezentarii in forma
standard a arborelui cu ponderi (ca in comanda TREE din sistemul de operare
DOS) sau textul SPECIE NECUNOSCUTA DE ARBORE daca datele de intrare nu conduc
la constructia unui arbore binar. Dupa fiecare solutie a unui test de date
se lasa o linie alba. Exemplu: Pentru fisierul de intrare 6 | 1 2 1 4 1 6 | 3 | 1
1 3 | 0
iesirea este: 6 4 2 1 1 2 1 1 2 1 1

SPECIE NECUNOSCUTA DE ARBORE

Timp de executie: maxim  ? sec/test
------------------------------------

Ziua 2    Problema 4 (Cadran - Victor Mitrana)

Multe sisteme de criptare clasice (Warenhouse, etc) folosesc un cadran pe
care se afla caractere, si doua limbi (ca la ceas) care se pot roti
impreuna pastrand intre ele un unghi fix. La rotirea limbilor, una din ele
arata caracterul din textul clar, iar cealalta - caracterul cu care se
cripteaza. Conditia pusa este aceea ca cele doua limbi sa nu arate niciodata
simultan caractere identice. Sa consideram un astfel de cadran pe care se
afla scrise circular n (10<=n<=5000) cifre (caracterele 0..9). Un sistem de
criptare este specificat printr-o pereche de numere (x,y) unde x (1<=x<n)
arata pozitia initiala pe cadran a unei limbi, iar y (x<y<=n) arata pozitia
initiala a celei de-a doua limbi. O miscare a limbilor inseamna deplasarea
lor simultana cu o pozitie in sensul acelor de ceasornic. Un sistem de
criptare (x,y) este viabil daca pentru orice secventa de n miscari
consecutive exista cel putin o pozitie in care cifrele indicate de cele doua
limbi sunt distincte. Problema cere ca fiind dat un cadran cu n cifre, sa se
 determine cate sisteme de criptare viabile sunt posibile. Intrare: Fisierul
de intrare, al carui nume se citeste de la tastatura contine pe prima linie
numarul n de cifre de pe cadran. Pe urmatoarele linii se afla n cifre, cate
20 pe o linie (inafara eventual de ultima linie), separate prin cate un
spatiu. Iesire: Se scrie pe ecran un numar care reprezinta numarul de sisteme
de criptare viabile pentru cadranul dat in setul de intrare. Exemplu: Pentru
fisierul de intrare 4 | 1 2 1 3 iesirea va fi 6

Timp de executie: 1 secunda/test
------------------------------

Ziua 2   Problema 5 (Din nou agricultura - Virgil Domocos)

In Valea lui Liman impartirea pamantului s-a incheiat. Bineinteles ca nu au
putut fi satisfacute doleantele taranilor; nici nu era posibil, avand in
vedere modul in care mai multi sateni solicitau aceleasi loturi. Dar, de la
guvern s-au deblocat fonduri, mlastinile au fost secate, taranii au primit
loturi de marimi egale cu cele cerute, titlurile de proprietate au fost
distribuite si toata lumea a fost multumita. Fiecare satean este
proprietarul unui lot de forma poligonala. Drumul de acces este foarte
intortochiat; el intra in zona agricola printr-un punct si, separand
permanent cate doua loturi, trece prin fiecare colt al fiecarui lot o
singura data, dupa care iese prin acelasi punct in care a intrat. Taranii
au cerut aceasta, in ideea de a strange in aceste colturi recolta de pe
loturile lor, pentru a fi carata acasa. Dar seara, stand de vorba la crasma
din sat, o vorba a lui Mos Stramba i-a pus pe ganduri. Fiecare colt in care
se scoate recolta de pe camp apartine mai multor loturi. Chiar si la fiecare
portiune de drum au acces direct doua loturi. De unde sa stie ei seara, cand
vor incarca in carute, cui apartine fiecare gramada ? Nu va fi asta un nou
prilej de discordie ? Au petrecut satenii multe seri la crasma, si au
consumat multa tarie, dezbatand aceasta problema, mai importanta pentru ei
decat marea privatizare. Pana la urma, au decis in felul urmator: a) Nu vor
cultiva decat grau, porumb, floarea soarelui si orz; b) Orice doua loturi
vecine (care au cel putin o latura comuna) cultiva produse diferite. Taranii
stiu ca este posibil sa faca aceasta; toti au absolvit scoala din sat. Ceea
ce trebuie numai este sa decida ce va semana fiecare. Construiti un program
care sa ii ajute. Intrare: Fisierul de intrare (cu numele citit la tastatura)
are urmatoarea forma: - Pe prima linie, un intreg pozitiv n (3<=n<=1000)
care reprezinta numarul de colturi (varfuri) ale loturilor; acestea sunt
marcate cu numerele 1..n. Drumul printre loturi trece consecutiv prin
nodurile 1,2,..,n,1. Sunt maxim 250 loturi, iar fiecare lot nu poate avea
mai mult de 100 colturi. Urmatoarele linii reprezinta fiecare colturile cate
unui lot; colturile sunt listate prin citirea in sensul acelor de ceasornic;
sfarsitul liniei este marcat cu end-of-line. Loturile sunt ordonate prin
ordinea scrierii lor: lotul 1, lotul 2, s.a.m.d Iesire: Fisierul de iesire
(recolta.out) va contine un sir (pe o singura linie) cu caracterele g
(grau), p (porumb), f (floarea soarelui) si o (orz). Al j-lea caracter din
sir va reprezenta tipul de plante cultivat pe al j-lea lot. Exemplu: Pentru
intrarea 7 1 2 3 7 3 4 5 6 7 1 7 6 5 o iesire posibila poate fi gfp

Timp de executie: 2 secunde/test.
----------------------------------------

Ziua 2   Problema 6 (La vanatoare - Mihai Oltean)

Doi prieteni A si B se hotarasc intr-o zi sa mearga la vanatoare de rate.
Datorita faptului ca numai A are pusca, se hotarasc sa traga alternativ.
Mai mult, pentru ca cel care trage sa nu se plictiseasca, si pentru ca nu
cumva unul din ei sa monopolizeze pusca, ei decid ca fiecare, cand ii vine
randul, sa traga maxim k gloante. Ajuns la locul de vanatoare,
neindemanaticul caine al lui B reuseste sa sperie toate ratele, care se
ridica in aer formand n stoluri. In acest moment, A (care avea pusca asupra
lui) incepe sa traga. Pentru a nu pierde timpul cu schimbarea directiei spre
un alt stol, fiecare vanator va trage doar asupra unui stol pe care il alege
de fiecare data cand pusca este la celalalt. Pana la urma, cei doi prieteni
fiind vanatori foarte buni (dovada fiind si faptul ca fiecare glont tras a
doborat cate o rata) reusesc sa omoare toate ratele din cele n stoluri. Acum
intra in actiune si trimis dupa ratele impuscate cainele lui B (A nu are
caine) care, din cauza faptului ca participa pentru prima data la o
vanatoare, s-a speriat la auzul primei impuscaturi si s-a asucns prin
tufisuri, iesind doar in momentul in care ultima rata este doborata.
Limitat in gandire (ca orice caine), acesta va crede ca vanatorul care a
doborat ultima rata le-a doborat si pe celelalte; deci ii va aduce acestuia
toate ratele. Presupunand ca sunteti A, gasiti (daca exista) o strategie de
impuscare a ratelor astfel incat sa fiti vanatorul caruia cainele ii va
aduce toata prada. Numele fisierului de intrare este joc.in si contine mai
multe seturi de date; anume: - pe liniile cu numar de ordine impar se afla n
si k (1<=n,k<=10000); - pe liniile cu numar de ordine par se afla numarul de
pasari din fiecare din cele n stoluri (n dat in linia precedenta); cele n
numere sunt intregi pozitive. Atentie: Toate seturile de date dintr-un
fisier alcatuiesc un pachet de date de intrare. Punctajele se acorda pe
pachete, adica pentru a primi punctajul atasat unui pachet trebuie sa
rezolvati corect toate seturile de date din el. Pentru a va usura munca,
comisia va pune la dispozitie un unit cu numele joc.tpu care contine
urmatoarele proceduri: StartJoc - este procedura pe care trebuie sa o
apelati inainte de a incepe un nou joc. DeclarStrategia(strategia:integer) -
este procedura pe care o apelati pentru a-i comunica unitului daca aveti sau
nu strategie sigura de castig. Parametrul strategia are valoarea 1 daca
aveti strategie sigura de castig si 0 in caz contrar.
MutareaMea(stol,nr:longint) - este procedura pe care o apelati pentru a-i
comunica unitului stolul si numarul de pasari din acel stol pe care le
doborati; MutareaTa(var stol,nr:longint) - este procedura pe care o apelati
pentru ca unitul sa va returneze mutarea pe care o va face calculatorul;
SfarsitJoc - este procedura pe care trebuie sa o apelati la sfarsitul
fiecarui joc (set de date). In cazul in care nu aveti strategie sigura de
castig, veti apela doar: StartJoc; DeclarStrategia(0); SfarsitJoc; In cazul in
care aveti strategie sigura de castig, jucati jocul cu unitul dat,
folosindu-va de procedurile de mai sus. Timpul de executie pentru
determinarea existentei strategiei sigure de castig este 1 secunda/test, iar
pentru jucat - 5 secunde/test.
